package com.Algorithm;

import java.util.Arrays;

/**
 * project : my-learn
 * <p> 桶排序 </p>
 *
 * @author yisl
 * @date 2022-07-09【星期六】
 **/
public class BuckSort {

    public static void main(String[] args) {
        int[] a={3,2,7,6,-1,7};
        System.out.println(Arrays.toString(buckSort(a)));
    }

    public static int[] buckSort(int[] a){
        int n = a.length;
        int[] b = new int[n];
        int min = a[0], max = a[0];
        for (int i = 0; i < n; i++) {
            max = Math.max(max, a[i]);
            min = Math.min(min, a[i]);
        }
        int buckSize = 10;
        int buckCount = (max -min)/buckSize +1;
        int[][] buck = new int[buckCount][0];
        for (int i = 0; i < n; i++) {
            int index = (b[i]-min)/buckSize;
            buck[index] = arrpend(buck[index], a[i]);
        }
        int idx =0;
        for (int[] c:buck){
            if(c.length==0)continue;
            Arrays.sort(c);
            for (int val : c) {
                b[idx++]=val;
            }
        }
        return b;
    }
    public static int[] arrpend(int[] a, int x){
        a = Arrays.copyOf(a, a.length+1);
        a[a.length-1] = x;
        return a;
    }



}
